#ifndef _STLINKLIST_H_
#define _STLINKLIST_H_

#include "SNode.hpp"
#include <iostream>

/**
 * @brief 
 * 带有尾节点的单链表,增加了空间复杂度,但是将尾节点的插入时间复杂度降低
 * @tparam ElemType 数据类型
 */
template <typename ElemType>
class STLinkList
{
private:
    /* data */
public:
    STLinkList(/* args */);
    STLinkList(const ElemType *elems, int n);
    STLinkList(const STLinkList &other);
    ~STLinkList();
    STLinkList &operator=(const STLinkList &e);
    void Clear();
    void Traverse(void (*visit)(const ElemType &e)) const;
    int GetLength() const;
    int InsertElem(const ElemType &e);        // 将元素添加到链表尾
    int InsertElem(int i, const ElemType &e); // 将元素添加到i的位置
    int DeleteElem(int i, ElemType &e);       // 删除位置i所在的元素,并且将删除状态返回,将删除元素数据存储在e
    int LocateELem(const ElemType &e) const;
    int GetElem(int i, ElemType &e) const;
    int SetELem(int i, const ElemType &e);

protected:
    SNode<ElemType> *head;
    SNode<ElemType> *tail;
    int length;
};

template <typename ElemType>
STLinkList<ElemType>::STLinkList()
{
    head = new SNode<ElemType>;
    tail = *head;
    length = 0;
}

template <typename ElemType>
STLinkList<ElemType>::STLinkList(const ElemType *elems, int n)
{
    head = new SNode<ElemType>;
    SNode<ElemType> *p = head;
    for (int i = 0; i < n; i++)
    {
        p->next = new SNode<ElemType>(elems[i]);
        p = p->next;
    }
    tail = *p;
    length = n;
}

template <typename ElemType>
STLinkList<ElemType>::STLinkList(const STLinkList &other)
{
    head = new SNode<ElemType>();
    SNode<ElemType> *p = head, *q = other.head->next;
    length = other.GetLength();
    for (int i = 0; i < length; i++)
    {
        p->next = new SNode<ElemType>(q->data);
        q = q->next;
        p = p->next;
    }
    tail = *p;
}

template <typename ElemType>
void STLinkList<ElemType>::Clear()
{
    length = 0;
    tail = *head;
    SNode<ElemType> *p = head->next;
    while (p)
    {
        head->next = p->next;
        delete p;
        p = head->next;
    }
}

template <typename ElemType>
void STLinkList<ElemType>::Traverse(void (*visit)(const ElemType &e)) const
{
    SNode<ElemType> *p = head->next;
    while (p)
    {
        (*visit)(p->data);
        p = p->next;
    }
    std::cout << "tranverse finished . " << '\n';
}

template <typename ElemType>
STLinkList<ElemType> &STLinkList<ElemType>::operator=(const STLinkList<ElemType> &other)
{
    Clear();
    length = other.length;
    SNode<ElemType> *p = head, *q = other.head->next;
    while (q)
    {
        p->next = new SNode<ElemType>(q->data);
        q = q->next;
        p = p->next;
    }
    tail = *p;

    return *this;
}

template <typename ElemType>
int STLinkList<ElemType>::GetLength() const
{
    return length;
}

template <typename ElemType>
int STLinkList<ElemType>::InsertElem(const ElemType &e)
{
    SNode<ElemType> *p = new SNode<ElemType>(e);
    tail->next = p;
    tail = p;
    length++;
    return 1;
}

template <typename ElemType>
int STLinkList<ElemType>::InsertElem(int i, const ElemType &e)
{
    if (i > length || i < 1)
        return 0;
    else
    {
        SNode<ElemType> *p = head, *q;
        for (int cnt = 1; cnt < i; cnt++)
        {
            p = p->next;
        }
        q = new SNode<ElemType>(e, p->next);
        p->next = q;
        length++;
        return 1;
    }
}

template <typename ElemType>
int STLinkList<ElemType>::DeleteElem(int i, ElemType &e)
{
    if (i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head, *q;
        for (int cnt = 1; cnt < i; cnt++)
        {
            p = p->next;
            /* code */
        }
        q = p->next;
        e = q->data;
        p->next = q->next;
        delete q;
        // 如果删除的是最后一个元素,则尾指针前移
        if (i == length - 1)
        {
            tail = p;
        }
        length--;
    }
}

template <typename ElemType>
int STLinkList<ElemType>::LocateELem(const ElemType &e)const
{
    SNode<ElemType> *p = head->next;
    int i = 1;
    while (p)
    {
        if(p->data == e)
        {
            return i;
        }else
        {
            p = p->next;
            i++;
        }
    }
}

template <typename ElemType>
int STLinkList<ElemType>::GetElem(int i,ElemType &e) const
{
    if(i < 1 || i > length)
        return 0;
    else
    {
        SNode<ElemType> *p = head->next;
        for (int  cnt = 1; cnt < i; cnt++)
        {
            p = p->next;
        }
        e = p->data;
        return 1;
    }
}

template <typename ElemType>
int STLinkList<ElemType>::SetELem(int i,const ElemType &e)
{
    if(i<1 || i>length)
        return 0;
    else
    {
        SNode<ElemType> *p = head->next;
        for (int cnt = 1; cnt < i; cnt++)
        {
            p = p->next;
        }
        p->data = e;
        return 1;
        
    }
}


#endif // !_STLINKLIST_H_
